The background art for the present invention is described.
Prior Art Technique 1
In digital data transmission, it is normally impossible for a receiver to receive a signal transmitted by a sender as it is due to the state of the channel and noises. The transmitted signal is converted into other form by the state of the channel and by noises. This converted form is received.
A model describing conversion of a signal on a channel is illustrated in FIG. 16. As shown in this figure, the signal is delayed on the channel. In addition, noises are adeed. Let X.sub.k be transmitted signal. The received signal r.sub.k is given by ##EQU1##
where L is the length of memory of the channel that delays the transmitted signal, C.sub.i is a tap coefficient, and w.sub.k is a noise sequence. The tap coefficient and the noise sequence are values determined by the characterstics of the channel. PA1 (1) First, the squares of errors from each branch (line segments in FIG. 19) are computed. PA1 (2) Then, a path indicating transitions of a state going to states (00, 10, 01, 11 in FIG. 19) at some instant is extracted. The branch metrics of branches forming the extracted path are summed up. In this way, the path metric is calculated. Note that the path metric is calculated for every path in every state. PA1 (3) The path metrics of the paths extracted from the states are compared. Such a comparison is made for every state. PA1 (4) The path found to have the least path metric by the comparisons is regarded as a path of maximum likelihood. The path and the path metric are stored in memory. This storing of paths and path metrics is performed for each individual state. PA1 (5) In the Viterbi algorithm, one is finally selected as a surviving path from plural paths going to some state.
The receiver receiving the signal r.sub.k estimates the transmitted signal from the received signal r.sub.k and from the tap coefficient c.sub.i.
The receiver, or a sequence estimator, convolves a candidate for the transmitted signal with known tap coefficients and calculates an estimated value (hereinafter referred to as a replica) of the received signal as follows: ##EQU2##
Furthermore, the receiver, or the sequence estimator, calculates the error power between the estimated value (replica) of the received signal calculated according to Eq. 2) and the actual received signal, using the following Eq. (3): ##EQU3##
The receiver searches for a transmitted signal candidate minimizing the error power given by Eq. (3) and estimates that this candidate is the transmitted signal.
Processing for estimating a sequence where the memory length of the channel is set to L=2 is described in detail. FIG. 17 illustrates a model of a sequence estimator that is best adapted for the case where the memory length of the channel is L=2. The sequence estimator is so constructed as to reproduce a model similar to a model of a channel. However, in the sequence estimator shown in FIG. 17, means for adding noises are omitted from the model of the channel.
Specifically, the sequence estimator comprises: a memory having the same memory length as the memory length for the channel and receiving estimated values of the transmitted signal; a multiplication means for multiplying an estimated value of the transmitted signal produced from the memory by given tap coefficients; an adder means for calculating an estimated value (replica) of the received signal by summing up the products produced by the multiplication means; an error-calculating means for producing the differences between the estimated value (replica) of the received signal produced from the adder means and the actual received signal; and a squares sum-calculating means for taking the sum of squares of values produced from the error-calculating means. The given tap coefficients at which the multiplication means is set are the same as the tap coefficients obtained from the characteristics of the channel.
A method of making maximum likelihood estimates by the sequence estimator described thus far is described.
First, candidates for a transmitted signal of sequence length N are obtained.
Then, the candidates for the transmitted signal are entered into the memory of the sequence estimator. The multiplication means multiplies signals produced from the memory by tap coefficients c.sub.1 and c.sub.2. The signal produced without via the memory is multiplied by a tap coefficient c.sub.0.
The adder means sums up the values produced by the multiplication means to obtain an estimated value (replica) of the received signal.
The difference-calculating means takes the difference between the estimated value (replica) of the received signal obtained by the adder means and the actually received signal.
The squares sum-calculating means takes the sum of squares of difference values produced from the difference-calculating means. The squares sum-calculating means sums up the squares of the differences between the estimated signal (replica) of the received signal and the received signal for every signal sequence.
Let N be the length of the transmission sequence length. There are 2.sup.N candidates for this transmitted signal. The above-described processing is performed for every candidate.
The maximum likelihood estimator estimates that the candidate for the transmitted signal minimizing the squares sum produced from the squares sum-calculating means is the transmitted signal.
Prior Art Technique 2
In the case of the maximum likelihood estimates as described above, the amount of calculation increases in proportion to a power of the transmission sequence length N. Accordingly, maximum likelihood estimates adopting a procedure known as the Viterbi algorithm are used. The Viterbi algorithm is described in detail by G. D. Forney, Jr. in "The Viterbi algorithm", Proc. IEEE, Vol.61, No.3, pp. 268-278 (March 1973).
In the case of the channel model of FIG. 18, the error electric power at instant k can be calculated if data about transmission at the present instant k and data about transmission performed two instants earlier are known.
In the maximum likelihood estimates using the Viterbi algorithm, a diagram (hereinafter referred to as a trellis diagram) describing information about transitions of data arising from combinations of data at two instants as shown in FIG. 19 is used.
In this trellis diagram of FIG. 19, combinations of data at two instants of time are connected by lines, taking account of the following characteristics.
It is assumed, for example, that a signal stored in memory at some instant is in state 00. At the next instant, the state makes a transition either to state 10 or to state 00. However, transition to state 01 or state 11 does not occur, because if a shift register in 000 is shifted one clock time, only 000 or 100 is obtained.
Accordingly, when combinations of data at two instants are connected by lines, states 00 and 10 are connected by a line. Also, states 00 and 00 are connected by a line. No line is drawn between states 00 and 01. No line is drawn between states 00 and 11.
The trellis diagram is created by taking account of the characteristics of transitions in this way. In FIG. 19, a line connecting states indicates a possibility of a transition. No connecting line means that transition cannot occur. A line indicating a transition of state is hereinafter referred to as a branch. In the trellis diagram of FIG. 19, both solid lines and dotted lines are put. The solid lines indicate that signal 0 is applied, producing a transition of a state. The dotted lines indicate that signal 1 is applied, resulting in a transition of a state.
If combinations of data at two instants are connected by a line as in the trellis diagram of FIG. 19, a combination of data at three instants can be determined. By making use of this, the error electric power can be found.
Then, the contents of processing of the Viterbi algorithm using the trellis diagram of FIG. 19 are described in detail.
The number of states is determined by the Viterbi algorithm in the manner described now. Let L be the transmission memory length. The number is 2.sup.L. That is, the number of states increases in proportion to a power of the transmission memory length L. The amount of calculation increases according to the number of states.
In the prior art technique 1, every candidate for the transmitted signal must be searched for. In contrast, application of the Viterbi algorithm can reduce the number of processing steps.
The procedure for the processing of the Viterbi algorithm at each instant is illustrated in FIG. 20.
In the description given below, state xx at each instant k is given by s[k, xx]. At instant k.sub.1, state xx occurs. A path through which a transition to state .smallcircle..smallcircle. occurs at instant k.sub.2 is given by s[k.sub.1, xx]/s[k.sub.2, .smallcircle..smallcircle.].
The squares of errors at each branch are referred to as branch metrics.
For instance, in the case of a branch connecting states s[0,00] and s[1,00], this branch indicates that data at three instants is 000. These items of data are multiplied by tap coefficients. The differences from the actual received signal are taken. The squares of the differences are taken. Thus, the squares of the errors are calculated.
The square of error at every branch is calculated by this method.
For example, paths going to s[2,00] include two paths, i.e., a path s[0,00]/s[1,00]/s[2,00] and a path s[0,11]/s[1,01]/s[2,00]. The path metrics of these two paths are calculated.
The path found to have the least path metric by the comparisons is referred to as a surviving path. The path metric of this surviving path is referred to as a surviving path metric.
For example, of paths going to state s[2,00], the path metric of the path s[0,00]/s[1,00]/s[2,00] is compared with the path metric of the path s[0,11]/s[1,01]/s[2,00]. The smaller path becomes a surviving path.
The Viterbi algorithm performs the processing described thus far at each instant of time.
The Viterbi algorithm is conducted using the trellis diagram of FIG. 19. The results are shown in FIG. 21, which shows surviving paths finally obtained.
At the final instant of time, the above-described processing has been conducted for 1 frame. A path having the least path metric is selected as final paths from the surviving paths. In FIG. 21, the paths indicated by solid lines and solid broken lines, respectively, are final paths.
The estimator estimates that a signal sequence obtained from the final path is the transmitted signal.
The maximum likelihood estimation using the Viterbi algorithm as described thus far is referred to as Maximum Likelihood Sequence Estimation (MLSE), as described by G. D. Forney, Jr., in "Maximum-likelihood sequence estimation of digital sequences in the presence of intersymbol interference", IEEE Trans. Inform. Theory, Vol. IT-18, No. 3, pp. 363-378 (May 1972).
In this MLSE, the number of states of the Viterbi algorithm is 2.sup.L, where L is the channel memory length. A procedure for uniquely filling values of the channel memory from branches indicating state transitions is the MLSE. FIG. 21 shows a model of the channel memory where L=5. When the MLSE is applied to this model, the number of states is 2.sup.5, i.e., 32.
Prior Art Technique 3
The above-described MLSE can reduce the amount of processing compared with prior art technique 1. However, the number of states increases in proportion to a power of the channel memory length L. Therefore, the amount of processing is still exorbitant.
In an attempt to solve this problem, a procedure known as Decision-Feedback Sequence Estimation (DFSE) has been proposed by A. Duel-Hallen et. al in "Delayed decision-feedback sequence estimation", IEEE Trans. Commun., Vol. COM-37, 5, pp. 428-436, May 1989.
This procedure known as DFSE is a modification of the processing of the aforementioned MLSE.
The difference in operation between the DFSE and MLSE is briefly described by referring to FIG. 15. In FIG. 15, the number of channel memories is 5. Therefore, in order to fill all candidates, it is necessary to create states by five memories. In this case of MLSE, the number of states is 32.
On the other hand, in the case of the DFSE, the number of channel memories is 5. We take notice of two memories as memories used to create states. However, where states are created by the two memories, data about the latter three symbols is insufficient to fill the channel memories. Accordingly, surviving paths connected to a state at instant k-1 are utilized. Values obtained from the surviving paths are used as the data about the latter three symbols.
Application of the DFSE described thus far can reduce the number of states from 32 down to 4.
The processing of the DFSE is described in detail by referring to FIG. 20, which illustrates generalized contents of processing of the DFSE at each instant of time.
&lt; Processing from Instant k=1 to 3&gt;
It is first assumed that data are known where k is negative and that every state exists under the condition k=0.
As can be seen from the trellis diagram of FIG. 19, either the path s[0,00]/s[1,00] or the path s[0,01]/s[1,00] is available in going to s[1,00]. Their path metrics are calculated and compared. Paths with smaller path metrics are selected as surviving paths. It is now assumed that the path s[0,00]/s[1,00] is selected as a surviving path.
Similarly, surviving paths going to states s[1,10], s[1,01] and s[1,11] are determined one by one.
By performing similar processing, surviving paths going to states are determined at instants k=2 and k=3.
By carrying out this processing, a surviving path shown in FIG. 2 is obtained up to instant k=3. Also, the path metrics of paths surviving up to k=3 are stored in memory.
&lt; Processing at Instant k=4&gt;
Processing for Calculating Branch Metrics: BMG-I
If state s[3,00]or state s[3,01] is available, state s[4,00] is obtained. Therefore, paths leading to the state s[4,00] include two paths, i.e., path s[0,01]/s[1,10]/s[2,01]/s[3,00]/s[4,00] and path s[0,01]/s[1,10]/s[2,11]/s[3,01]/s[4,00].
This path s[0,01]/s[1,10]/s[2,01]/s[3,00]/s[4,00] produces a candidate for a transmitted sequence "000101" at instant k=4. The path s[0,01]/s[1,10]/s[2,11]/s[3,01]/s[4,00] results in a candidate for a transmitted sequence "001101" at instant k=4. The branch metric at k=4 is calculated from this value.
Processing for Calculating Path Metrics: ADD-I
The path metrics of the above-described paths going to the state s[4,00] are calculated.
Path metrics up to k=3 were calculated and stored in memory. A branch metric at k=4 is now calculated and added to the stored metrics, thus producing path metrics. In particular, in the case of path s[0,01]/s[1,10]/s[2,01]/s[3,00]/s[4,00], a branch metric is added to the path metric about state s[3,00]. In the case of the path s[0,01]/s[1,10]/s[2,11]/s[3,01]/s[4,00], a branch metric is added to the path metric about state s[3,01].
Similar processing is performed for states s[4,10], s[4,01] and s[4,11].
Processing for Comparing Path Metrics: CMP-I
Then, the path metrics of two paths going to the state s[4,00] calculated in ADD-I are compared. That is, the path metric of the path s[0,01]/s[1,10]/s[2,01]/s[3,00]/s[4,00] is compared with the path metric of the path s[0,01]/s[1,10]/s[2,11]/s[3,01]/s[4,00]. This comparison of the path metrics is made by taking the difference between the selected path metrics (Processing for Selection: SEL).
Of the path metric of the path s[0,01]/s[1,10]/s[2,01]/s[3,00]/s[4,00] and the path metric of the path s[0,01]/s[1,10] /s[2,11]/s[3,01]/s[4,00], the path having a smaller path metric is selected as a surviving path going to s[4,00].
The processing of CMP-I and SEL described thus far is performed also about the states s[4,10 ], s[4,01], and s[4,11].
This processing is performed at every instant after k=5. The above-described processing is performed for about 1 frame. The path metrics of surviving paths obtained at the final instant about states are compared. The path having the least path metric is selected. This selected path is the final path.
The transmitted sequence is selected from the final path. The sequence estimator estimates that the obtained transmitted sequence is a sequence transmitted by the sender.
FIG. 22 is a block diagram of a sequence estimator performing the Viterbi algorithm illustrated in FIG. 20.
In FIG. 22, 1B is a branch metric-calculating portion. Indicated by 2B is a bus metric-calculating portion mounted on the output side of the branch metric-calculating portion 1B. Indicated by 4B is a compare-select processing portion mounted on the output side of the path metric-calculating portion 2B.
Indicated by 5 is a path metric memory mounted on the output side of the compare-select processing portion 4B and on the input side of the path metric-calculating portion 2B. Indicated by 6 is a surviving path memory connected with the branch metric-calculating portion 1B and with the compare-select processing portion 4B.
A received signal input terminal 7 receives a received signal. A channel characteristic input terminal 8 receives the characteristics of the channel, e.g., tap coefficients or the like described in the above-described embodiments. An output line 9 delivers surviving paths stored in the surviving path memory 6.
Then, the operation of this sequence estimator is described, corresponding to the contents of processing of FIG. 20. The branch metric-calculating portion 1B performs the BMG-I shown in FIG. 20.
The path metric-calculating portion 2B receives the branch metric calculated by the branch metric-calculating portion 1B and performs the ADD-I illustrated in FIG. 20.
The compare-select processing portion 4B receives the plural path metrics calculated by the path metric-calculating portion B and performs the CMP-I and SEL.
During the processing of SEL by the compare-select processing portion 4A, obtained surviving paths are stored in the surviving path memory 6. In addition, the path metrics of the surviving paths are stored in the path metric memory 5.
In the DFSE described thus far, attention is paid to the states of only two memories. Obviously, maximum likelihood is not obtained. Consequently, the characteristics of the MLSE are deteriorated. For example, in the non-minimum phase conditions illustrated in FIG. 14(b), signal components of memories to which the DFSE pays attention are reduced to a greater extent than signal components corresponding to other memories. Therefore, errors are introduced in selecting surviving paths. If an error is produced once in selecting surviving paths, the error occurs repeatedly. This phenomenon is known as error propagation. Thus, the characteristics are deteriorated greatly.
On the other hand, the MLSE has ideal characteristics but is impractical because of an exorbitant amount of calculation.